| （初学者）素数计算法 | 您所在的位置：网站首页 › network is not of reach › （初学者）素数计算法 |
（初学者）素数计算法
|
前言
记得我刚开始学习OI的时候接触到的最早的算法莫过于素数算法。当然了，素数这个知识小学的时候我们就已经有所学习了。 质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。 当时我一直有一个疯狂的设想，就是编写一个程序把我能算出来的素数都算出来。因为当时水平有限，用C语言打印了一个一百万以内的质数表都用了好几秒的时间，所以说我一直希望能有一种方法又快而又准确地求出很大范围之内的素数。 1.朴素的质数验证法我们当时学的最早的那种方法就是“朴素算法”，这是一个用来验证一个数是否是质数的算法。它的原理就是和小学数学书上所写是一模一样的：如果这个数是2，那么它是质数；如果这个数大于2，那么就判断它是否能整除从2到这个数减一中的所有数，如果能则是质数。 代码也是非常简洁的（simple and stupid）： bool IsPrime(int NumToCheck)//判断一个数是否是质数 { if(NumToCheck if(NumToCheck for(int i=2;i CheckTime(10000); CheckTime(100000); CheckTime(1000000); CheckTime(10000000);//分别对以上的四组数据进行时间测试 system("pause"); return 0; }当数据范围超过一百万时，这个算法就显得“捉襟见肘”了。有图有真相：
所以，我们也许需要一些更高端的方法来弥补这个算法的缺点。而这个算法就是著名的： 3.（埃拉托斯特尼筛法）埃氏筛法它并不像朴素一样，对每个数进行判断，因为它是一种“筛法”。就像是一个“筛子”中有一大堆数，每次把其中我确定出来的不是素数的数从“筛子”里筛出，最后剩下的就是我想要的素数了。首先，二是素数。然后每当我确定出一个素数，就把所有它的倍数从这个筛子里筛出。代码如下： bool IsPrimeTable[100000001];//IsPrimeTable[i]表示i是否在筛子中 void PrimeSelect(int NumMax)//筛法 { IsPrimeTable[0]=IsPrimeTable[1]=0;//0和1排除 for(int i=2;i PrimeTable[++PrimeCount]=thePrime; } void PrimeSelect(int maxNum)//欧拉筛法 { vis[0]=vis[1]=vis[2]=1; AddPrime(2);//把2加到质数表 for(int i=3;i vis[i*PrimeTable[j]]=1;//把 这个数 与 所有已知质数 的积 "筛出" if(i%PrimeTable[j]==0)//关键在这里,好好想想为什么要这么写 break; } } }欧拉筛法就是用这句话实现了“每个合数”只被筛出一次。 if(i%PrimeTable[j]==0)break;//其中i为任意数，PrimeTable[j]一定是一个质数。 （请立刻打开你的脑洞，因为下面的这段话不是很好理解。） 对于每一个大于1的数，我在它身上乘一个质数，得到的结果一定是一个合数。对于一个大于1的数，我在它身上乘上一个它自己的最小质因子，得到的合数的最小质因子，仍为原数的最小质因子。同理，让一个大于1的数乘上一个小于它最小质因子的质数，那么得到的新的合数的最小质因子一定是我乘上去的这个新的质数。因为PrimeTable中的质数是从小到大储存的，所以第一次满足关系式(i%PrimeTable[j]==0)的时候，PrimeTable[j]恰好为i的最小质因子。这样，我们就保证了每一个合数只能被它的最小质因子删去，故复杂度为O（n）。 再让我们探究一下欧拉筛法的运算效率。为了计算它的运行速度，我写了这样的一个程序： void CheckTime(int maxNum)//计算时间 { for(int i=0;i //初始化的内容写在这里 time_t start_t=clock();//取开始时间 //调用算法程序 time_t end_t=clock();//去结束时间 double lastTime=double(end_t-start_t)/CLOCKS_PER_SEC;//求得用时 //注意:一定要用double变量,这样就能精确到小数点后三位(更精确的方法我也不会了) cout |
【本文地址】